from typing import *
from heapq import *


# 通过 292 ms	16.6 MB	Python3
class Solution:

    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
        if (grid[0][0] == 1):
            return -1
        m, n = len(grid), len(grid[0])
        visit = [[False] * n for _ in range(m)]
        visit[0][0] = True
        q = [(1, 0, 0)]
        heapify(q)
        d8 = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0),
              (1, 1)]
        while len(q) > 0:
            s, x, y = heappop(q)
            if x == m - 1 and y == n - 1:
                return s
            for i, j in d8:
                nx, ny, ns = x + i, y + j, s + 1
                if nx >= 0 and nx < m and ny >= 0 and ny < n and grid[nx][
                        ny] == 0 and not visit[nx][ny]:
                    visit[nx][ny] = True
                    heappush(q, (ns, nx, ny))
        return -1


# 执行用时：244 ms, 在所有 Python3 提交中击败了84.20%的用户

# 内存消耗：16.6 MB, 在所有 Python3 提交中击败了23.70%的用户

# 通过测试用例：89 / 89


class Solution:

    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
        if (grid[0][0] == 1):
            return -1
        m, n = len(grid), len(grid[0])
        visit = [[False] * n for _ in range(m)]
        visit[0][0] = True
        q = Deque([(1, 0, 0)])
        d8 = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0),
              (1, 1)]
        while len(q) > 0:
            s, x, y = q.popleft()
            if x == m - 1 and y == n - 1:
                return s
            for i, j in d8:
                nx, ny, ns = x + i, y + j, s + 1
                if nx >= 0 and nx < m and ny >= 0 and ny < n and grid[nx][
                        ny] == 0 and not visit[nx][ny]:
                    visit[nx][ny] = True
                    q.append((ns, nx, ny))
        return -1


[(-1, 0), (0, 1), (1, 0), (0, -1)]
[(-1, -1), (-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1)]
